package redblack;


@SuppressWarnings({"unchecked"})
public class RBNode<T extends Comparable<T>>
{
	public static final RBNode NULL_NODE = null; 
	
	public static final boolean RED = false;
	public static final boolean BLACK = true;
	
	public RBNode<T> parent, left, right;
	public boolean color;
	
	public T value;
	
	/**
	 * Creates the node and does the insertion stuff.<br>
	 * Watch out! Parent need to be set.
	 */
	public RBNode(T value, boolean color)
	{
		this.value = value;
		this.parent = NULL_NODE;
		this.color = color;
	}
	
	///////////////////////////////////////////////////////////////////////////
	// INSERTION
	///////////////////////////////////////////////////////////////////////////
	
	void insert(T value, RBTree<T> tree)
	{
		int compare = value.compareTo(this.value);
		if (compare <= 0) {
			if (left != null) {
				left.insert(value, tree);
			}
			else {
				RBNode<T> newNode = new RBNode<T>(value, RED);
				linkLeft(newNode);
				 // can call case2, as there is a necessarily a p.
				newNode.insertCase2(tree);
			}
		}
		else {
			if (right != null) {
				right.insert(value, tree);
			}
			else {
				RBNode<T> newNode = new RBNode<T>(value, RED);
				linkRight(newNode);
				newNode.insertCase2(tree);
			}
		}
	}
	
	private void insertCase1(RBTree<T> tree)
	{
		if (parent == NULL_NODE) {
			color = BLACK;
		}
		else {
			insertCase2(tree);
		}
	}
	
	private void insertCase2(RBTree<T> tree)
	{
		if (parent.color == BLACK) {
			return;
		}
		else {
			insertCase3(tree);
		}			
	}
	
	private void insertCase3(RBTree<T> tree)
	{
		if (uncle() != null && uncle().color == RED) {
			parent.color = BLACK;
			uncle().color = BLACK;
			grandpa().color = RED;
			
			grandpa().insertCase1(tree);
		}			
		else {
			insertCase4(tree);
		}
	}
	
	private void insertCase4(RBTree<T> tree)
	{
		if (isRightChild() && parent.isLeftChild()) {
			parent.rotateLeft(tree);
			left.insertCase5(tree);
		}
		else if (isLeftChild() && parent.isRightChild()) {
			parent.rotateRight(tree);
			right.insertCase5(tree);
		}
		else {
			insertCase5(tree);
		}
	}
	
	private void insertCase5(RBTree<T> tree)
	{
		parent.color = BLACK;
		grandpa().color = RED;
		
		if (isLeftChild() && parent.isLeftChild()) {
			grandpa().rotateRight(tree);
		}
		else { // if (isRightChild() && parent.isRightChild())
			grandpa().rotateLeft(tree);
		}
	}
	
	///////////////////////////////////////////////////////////////////////////
	// DELETION
	///////////////////////////////////////////////////////////////////////////
	
	boolean delete(T value, RBTree<T> tree)
	{
		int compare = value.compareTo(this.value);
		
		if (compare == 0)
		{
			this.delete(tree);
			return true;
		}
		else if (compare < 0 && left != NULL_NODE)
		{
			return left.delete(value, tree);
		}
		else if (compare > 0 && right != NULL_NODE)
		{
			return right.delete(value, tree);
		}
		else {
			return false;
		}
	}
	
	private void delete(RBTree<T> tree)
	{
		RBNode<T> toDelete = this;
		
		// two children; move the successor (or predecessor) into
		// the deleting node; then we delete the successor
		if (toDelete.left != null && toDelete.right != null) {
			RBNode<T> successor = toDelete.getSuccessor();
			toDelete.value = successor.value;
			toDelete = successor;
		}

		// now we check one of the two cases: (leaf) or (1/2 children)
		RBNode<T> replacement = (toDelete.left != NULL_NODE) ? 
				(toDelete.left) : (toDelete.right);
			
		// at least one child
		if (replacement != NULL_NODE) {
			// delete the node
			replacement.parent = toDelete.parent;
			
			if (toDelete.parent == NULL_NODE) {
				tree.setRoot(replacement);
			}
			else if (toDelete.isLeftChild()) {
				toDelete.parent.left = replacement;
			}
			else { // current.isRightChild()
				toDelete.parent.right = replacement;
			}
			
			if (toDelete.color == BLACK) {
				replacement.fixAfterDeletion(tree);
			}
		}
		// no children and no parent; should never happen
		else if (toDelete.parent == NULL_NODE) {
			tree.setRoot(NULL_NODE);
		}
		// no children and parent
		else {
			if (toDelete.color == BLACK) {
				toDelete.fixAfterDeletion(tree);
			}
			
			if (toDelete.parent != NULL_NODE) {
				toDelete.unlink();
			}
		}
	}
	
	private void fixAfterDeletion(RBTree<T> tree)
	{
		final RBNode<T> root = tree.getRoot();
		RBNode<T> current = this;
		
        while (current != root && current.color == BLACK) {
            if (current.isLeftChild()) {
                RBNode<T> sibling = current.parent.right;

                if (sibling.color == RED) {
                    sibling.color = BLACK;
                    current.parent.color = RED;
                    current.parent.rotateLeft(tree);
                    sibling = current.parent.right;
                }

                if (sibling.isLeftBlack() && sibling.isRightBlack()) {
                	sibling.color = RED;
                    current = current.parent;
                }
                else {
                    if (sibling.isRightBlack()) {
                    	sibling.left.color = BLACK;
                        sibling.color = RED;
                        sibling.rotateRight(tree);
                        sibling = current.parent.right;
                    }
                    sibling.color = current.parent.color; 
                    current.parent.color = BLACK;
                    sibling.right.color = BLACK;                    
                    current.parent.rotateLeft(tree);
                    current = root;
                }
            }
            else { // symmetric
                RBNode<T> sibling = current.parent.left;

                if (sibling.color == RED) {
                    sibling.color = BLACK;
                    current.parent.color = RED;
                    current.parent.rotateRight(tree);
                    sibling = current.parent.left;
                }

                if (sibling.isRightBlack() && sibling.isLeftBlack()) {
                    sibling.color = RED;
                    current = current.parent;
                }
                else {
                    if (sibling.isLeftBlack()) {
                        sibling.right.color = BLACK;
                        sibling.color = RED;
                        sibling.rotateLeft(tree);
                        sibling = current.parent.left;
                    }
                    sibling.color = current.parent.color;
                    current.parent.color = BLACK;
                    sibling.left.color = BLACK;
                    current.parent.rotateRight(tree);
                    current = root;
                }
            }
        }

        current.color = BLACK;
	}
	
    private boolean isLeftBlack() {
    	return left == NULL_NODE || left.color == BLACK;
    }

    private boolean isRightBlack() {
    	return right == NULL_NODE || right.color == BLACK;
    }

	private void rotateRight(RBTree<T> tree)
	{
		RBNode<T> newTop = left;
		
		linkLeft(newTop.right);
		
		if (parent != NULL_NODE) {
			if (isLeftChild()) parent.linkLeft(newTop);
			else parent.linkRight(newTop);
		}
		else {
			newTop.parent = NULL_NODE;
			tree.setRoot(newTop);
		}
		
		newTop.linkRight(this);
	}
	
	private void rotateLeft(RBTree<T> tree)
	{
		RBNode<T> newTop = right;
		
		linkRight(newTop.left);
		
		if (parent != NULL_NODE) {
			if (isLeftChild()) parent.linkLeft(newTop);
			else parent.linkRight(newTop);
		}
		else {
			newTop.parent = NULL_NODE;
			tree.setRoot(newTop);
		}
		
		newTop.linkLeft(this);
	}

    ///////////////////////////////////////////////////////////////////////////
	// HELPERS
	///////////////////////////////////////////////////////////////////////////
	
	/** @param node nullable */
	private void linkRight(RBNode<T> node)
	{
		right = node;
		if (node != null) node.parent = this;
	}
	
	/** @param node nullable */
	private void linkLeft(RBNode<T> node)
	{
		left = node;
		if (node != null) node.parent = this;
	}
	
	private void unlink()
	{
		if (isLeftChild()) {
			parent.left = NULL_NODE;
		}
		else {
			parent.right = NULL_NODE;
		}
		// optional
		parent = NULL_NODE;
	}
	
	private boolean isRightChild()
	{
		return this == parent.right; 
	}
	
	private boolean isLeftChild()
	{
		return this == parent.left; 
	}
	
	private RBNode<T> grandpa()
	{
		// null case never happens
		return parent.parent;
	}
	
	private RBNode<T> uncle()
	{
		if (grandpa().left == parent)
			return grandpa().right;
		else
			return grandpa().left;
	}
	
	private RBNode<T> getSuccessor()
	{
		RBNode<T> current = this;
		
		// go down-left the right subtree
		if (current.right != NULL_NODE) {
            current = current.right;
			while (current.left != NULL_NODE)
				current = current.left;
		}
		// go up, until we're going upper-left
		else {
			RBNode<T> last = current;
			current = current.parent;
			while (current != NULL_NODE && last == current.right) {
				last = current;
				current = current.parent;
			}
		}
	
		return current;
	}
	
	@Override
	public String toString()
	{
		String colorStr = (color == BLACK) ? ("B") : ("R"); 
		return String.format("%s[%s]", value, colorStr);
	}
}
